package com.dy.分类.动态规划._300_最长上升子序列;
/*
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 */

import java.util.Arrays;

/**
 * 思路：
 * dp
 * dp[i]表示以第i个元素结尾时的最长上升序列的长度
 * 为了加快查找速度，可以用二分法
 */
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int dp[] = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            //每次都要初始化自己,如果比前面的都小，自己就是1
            dp[i] = 1;
            //此时寻找dp[j], 0<j<i-1中，第j个数比第i数小的，让dp[i] = Math.max(dp[j]+1,dp[i])
            for (int j = 0; j < i; j++) {
                //找到了上升空间
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * 贪心+栈，栈中存的是长度为n时的最小的值
     * 栈中先加入 nums[0]
     * 从1 遍历到n-1,当nums[i]大于栈顶元素时，直接push
     * 否则：
     * 从栈底遍历至栈顶，找到比nums[i]大的数，替换,最终栈的长度就是最长上升子序列的长度
     */
    public int lengthOfLIS2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int stack[] = new int[nums.length + 1];
        stack[1] = nums[0];
        int len = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > stack[len]) {
                stack[++len] = nums[i];
            } else {
                int place = Arrays.binarySearch(stack,0,len-1,nums[i]);
//                int start = 1, end = len;
//                while (start <= end) {
//                    int mid = start + (end - start) / 2;
//                    if (stack[mid] == nums[i]) {
//                        start = mid;
//                        break;
//                    }
//                    else if (stack[mid] < nums[i]) start = mid + 1;
//                    else {
//                        end = mid - 1;
//                    }
//                }
                place  = place<0?-(place+1):place;
                stack[place] = nums[i];
            }
        }
        return len;
    }


    public static void main(String[] args) {
        int nums[] = {3,5,6,2,5,4,19,5,6,7,12};
        int k=0;
        k=Arrays.binarySearch(new int[]{1,3,5,7,9},8);
        System.out.println((k<0?-(k+1):k));
       // Solution solution = new Solution();
//        solution.lengthOfLIS2(nums);
    }

    public int lengthOfLIS3(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int len = 0;
        for(int i = 0; i < nums.length; i++) {
            int index = binarySearch(dp, len, nums[i]);
            dp[index] = nums[i];
            if(index == len) len++;
        }
        return len;
    }

    public static int binarySearch(int[] dp, int h, int val) {
        int l = 0;
        while(l < h) {
            int mid = (l + h) / 2;
            if(dp[mid] == val) return mid;
            else if(dp[mid] < val) l = mid + 1;
            else h = mid;
        }
        return l;
    }
}
